package a09_贪心算法;

import java.util.HashMap;
import java.util.Map;

//情况1：客户支付5，直接收下
//情况2：客户支付10，只能用5来找零
//情况3：客户支付20，10+5找零(局部最优，5更通用) 5+5+5找零
public class a13_柠檬水找零 {
    public static void main(String[] args) {
        a13_柠檬水找零 test = new a13_柠檬水找零();
        boolean b = test.lemonadeChange(new int[]{5,5,10,10,20});
    }
    public boolean lemonadeChange(int[] bills) {
        int five = 0;
        int ten = 0;
        int twenty = 0;
        for (int i = 0; i < bills.length; i++) {
            if(bills[i] == 5){
                //直接收钱
                five++;
            }else if(bills[i] == 10){
                //5来找零
                if(five == 0){
                    return false;
                }else {
                    five--;
                }
                //收下10
                ten++;
            }else{//20
                if(ten > 0){
                    ten--;
                    if(five == 0){
                        return false;
                    }else {
                        five--;
                    }
                }else {
                    if (five < 3) {
                        return false;
                    }else {
                        five -= 3;
                    }
                }
                //收下20
                twenty++;
            }
        }
        return true;
    }

}
